#include<stdio.h>

//对数据进行调整
//对指定下标为start的根节点进行调整
//arr:数组的首地址
//start:需要进行调整的子树的根节点的下标
//end:整个数组的元素数量
void heapAdjust(int *arr,int start,int end)
{
    //先保存需要调整的第一个节点的值
    int tmp = arr[start];
    //i就是需要调整的根节点的左子节点(下标是从0开始的)
    //i<=end    保证i的左子树存在
    for(int i = 2*start+1;i<=end;i = 2*i+1)
    {
        //右子节点存在,并且左子节点的值小于右子节点
        if(i < end && arr[i] < arr[i+1])
        {
            i++;  
        }
        //i一定是指向左右孩子中的最大值
        if(arr[i] > tmp)
        {
            arr[start] = arr[i];
            arr[i] = tmp;
            start = i;
        }else 
        {
            break;
        }
    }
}

//推排序
void HeapSort(int arr[],int len)
{
    //第一次构建大根堆(从最后一个非叶子节点开始调整)
    //因为第一次是完全无序的,每一个非叶子节点都需要进行处理
    for(int i=len/2-1;i>=0;i--)
    {
        heapAdjust(arr,i,len-1);
    }
    //将第一个节点和最后一个节点交换
    for(int i=0;i<len-1;i++)   //len个元素,需要选出len-1个最大值
    {
        int tmp = arr[0];
        arr[0] = arr[len-1-i];
        arr[len-1-i] = tmp;
        heapAdjust(arr,0,len-2-i);
    }
}


int main()
{
    //待排序数组
    int a[] = {1,5,4,6,2,3,8,9,7,12,45,35,26};

    //推排序
    HeapSort(a,sizeof(a)/sizeof(a[0]));

    for(int i = 0;i<sizeof(a)/sizeof(a[0]);i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

    return 0;
}